"""
    http://projecteuler.net/problem=5
    
    2520 is the smallest number that can be divided by each of the numbers
    from 1 to 10 without any remainder.

    What is the smallest positive number that is evenly divisible by all of
    the numbers from 1 to 20?
"""
import time



def timeit(f):
    def timer():
        t0 = time.time()
        returned = f()
        print "time %s: %.6f" % (f, time.time() - t0)
        return returned
    return timer


@timeit    
def test_case():
    expected = 2520
    max_divisor = 10
    smallest_product = get_common_prime_product(max_divisor)
    
    assert divisible_by_each_under(smallest_product, max_divisor), \
        "smallest product %s is not divisible by each number between 1 and %s" % (
            smallest_product, max_divisor)
    assert smallest_product == expected, "smallest_product %s != expected %s" % (
            smallest_product, expected)
    print "test case succeeded! %d" % (smallest_product)

    
@timeit
def solution():
    return get_common_prime_product(20)


def prime_product(n):
    primes = get_primes_under(n)
    return multiply(primes)
    
    
def get_common_prime_product(n):
    common_primes = get_common_primes(n)
    #print common_primes
    return multiply_common_primes(common_primes)
    
    
def get_common_primes(n):
    common_prime_bag = {}
    
    for i in xrange(1, n+1):
        prime_count = get_prime_count(i)
        for prime in prime_count:
            if prime not in common_prime_bag or (
                common_prime_bag[prime] < prime_count[prime]):
                common_prime_bag[prime] = prime_count[prime]
                
    return common_prime_bag


def get_prime_count(n):
    primes = get_primes(n)
    return list_to_bag(primes)
    
    
def get_primes(number):
    for n in range(2, number):
        if number % n == 0:
            return get_primes(n) + get_primes(number / n)
    return [number]
    
    
def multiply_common_primes(prime_bag):
    product = 1
    for prime, count in prime_bag.items():
        item_product = multiply([prime] * count)
        product = product * item_product
    return product
    
    
def list_to_bag(seq):
    bag = {}
    for n in seq:
        if n not in bag:
            bag[n] = 1
        else:
            bag[n] += 1
    return bag
    
    
def get_primes_under(n):
    primes = []
    
    for i in xrange(1, n+1):
        if is_prime(i):
            primes.append(i)
            
    return primes


def is_prime(n):
    if n == 1:
        return True
    
    for i in range(2,n):
        if n % i == 0:
            return False
    return True


def multiply(seq):
    product = 1
    for n in seq:
        product = product * n
    return product


def divisible_by_each_under(number, max_):
    for n in range(1, max_):
        if number % n != 0:
            raise ValueError("%d does not divide evenly into %d" % (
                n, number))
    return True



if __name__ == '__main__':
    test_case()
    print solution()
    